﻿using System;
using Algoritmia.Utils;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Sorting
{
    public class InPlaceInsertionSorter<T> : IInPlaceSorter<T>
    {
        #region IInPlaceSorter<T> Members

        public void Sort(IList<T> list, Comparison<T> comparison = null)
        {
            comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);

            for(var i = 1; i < list.Count; i++)
            {
                T x = list[i];
                var j = i - 1;
                while ( j >= 0 && comparison(x,list[j]) < 0)
                {
                    list[j + 1] = list[j];
                    j--;
                }
                list[j + 1] = x;
            }
   
        }

        #endregion
    }
}
